package com.itheima.binarysearch;

public class BinarySearchDemo {
    /*
        1. 定义两个变量，表示要查找的范围。默认 min = 0， max = 最大索引
        2. 循环查找，但是 min <= max
        3. 计算出 mid
        4. 判断 mid 位置的元素是否为要查找的元素，如果是直接返回对应索引
        5. 如果要查找的值在 mid 的左半边，那么 min 值不变， max = mid - 1，继续下次循环查找
        6. 如果要查找的值在 mid 的右半边，那么 max 值不变， min = min + 1，继续下次循环查找
        7. 当 min > max 时，表示要查找的元素在数组中不存在，返回-1
     */
    public static void main(String[] args) {
        int[] arr = {1, 3, 9, 11, 13, 15, 19, 23, 37, 39, 40, 45, 47, 51, 53, 57, 66};
        int number = 15;

        int index = binarySearchForIndex(arr, number);
        System.out.println(index);
    }

    private static int binarySearchForIndex(int[] arr, int number) {
        // 定义查找范围
        int min = 0;
        int max = arr.length - 1;
        // 循环查找
        while (min <= max) {
            // 计算中间位置
            int mid = (min + max) >> 1;
            // mid指向的元素大于number
            if (arr[mid] > number) {
                max = mid - 1;
            } else if (arr[mid] < number) {
                // mid指向的元素小于number
                min = mid + 1;
            } else {
                // mid指向的元素等于number
                return mid;
            }
        }
        return -1;
    }
}